package arrray;

import java.util.Arrays;

/**
 * @author huangxianjin
 * @date 2025/8/19 23:39
 * @description "分发糖果"
 */
public class LC_135 {
    //思想：我们先找从左到右满足最少的糖果，再找从右到左的，最后取两边都满足的值(就是最大值)
    public int candy3(int[] ratings) {
        int len = ratings.length;
        int[] left = new int[len];
        int[] right = new int[len];

        //填充数组
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);

        //从左到右遍历
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }

        //从右到左遍历
        for (int j = len - 2; j >= 0; j--) {
            if (ratings[j] > ratings[j + 1]) {
                right[j] = right[j + 1] + 1;
            }
        }

        //取左右中的最大值
        int res = 0;
        for (int k = 0; k < len; k++) {
            res += Math.max(left[k], right[k]);
        }
        return res;
    }

    //大佬做法-贪心算法
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int i = 1; i < ratings.length; i++)
            if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        int count = left[ratings.length - 1];
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            count += Math.max(left[i], right[i]);
        }
        return count;
    }

    //官方做法-两次遍历
    public int candy2(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int right = 0, ret = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 1;
            }
            ret += Math.max(left[i], right);
        }
        return ret;
    }
}
